﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Threading;
using System.Xml;
using Jay.Sc2.Bof.Lib.Action;
using Jay.Sc2.Bof.Lib.State;
using Jay.Sc2.Bof.Lib.Tools;

namespace Jay.Sc2.Bof.Lib
{
	public interface IReproducer : IEquatable<IReproducer>
	{
		ICollection<IActionList> Reproduce(IActionList father, IActionList mother);
		string Name { get; }
	}
	public class DefaultReproducer : IReproducer
	{
		public ICollection<IActionList> Reproduce(IActionList father, IActionList mother)
		{
			List<IActionList> list = new List<IActionList>();
			list.Add(father);
			list.Add(mother);
			return list;
		}
		public string Name { get { return "Default"; } }
		public bool Equals(IReproducer other) { return GetType().Equals(other.GetType()); }
	}
	public class NewBuildReproducer : IReproducer
	{
		public static readonly NewBuildReproducer Instance = new NewBuildReproducer();
		private int count = 2;
		private Random rand = new Random();
		public IGoal m_Goal;
		public List<IAction> m_NeededActions;
		public ICollection<IActionList> Reproduce(IActionList father, IActionList mother)
		{
			List<IActionList> result = new List<IActionList>();
			for (int c = 0; c < count; c++)
			{
				ActionList al = new ActionList(father.Race);
				foreach (IState state in m_Goal)
				{
					IActionList tmp = state.BasicBuildOrder;
					if (tmp != null) al.AddRange(tmp);
				}
				al.AppendMissingAndRemoveExceeding(m_NeededActions);
				result.Add(al);
			}
			return result;
		}

		public string Name { get { return "NewBuild"; } }
		public bool Equals(IReproducer other) { return GetType().Equals(other.GetType()); }
	}
	public class RandomReproducer : IReproducer
	{
		private Random rand = new Random();
		public ICollection<IActionList> Reproduce(IActionList father, IActionList mother)
		{
			List<IActionList> list = new List<IActionList>();
			int max = Math.Max(father.Count, mother.Count);
			ActionList al1 = new ActionList(father.Race);
			ActionList al2 = new ActionList(father.Race);
			for (int c = 0; c < max; c++)
			{
				IAction a1 = null;
				IAction a2 = null;
				if (c < father.Count) a1 = father[c];
				if (c < mother.Count) a2 = mother[c];
				bool takeFatherAction = (rand.Next(2) == 0);
				if (takeFatherAction)
				{
					if (a1 != null) al1.AddAction(a1);
					if (a2 != null) al2.AddAction(a2);
				}
				else
				{
					if (a1 != null) al2.AddAction(a1);
					if (a2 != null) al1.AddAction(a2);
				}
			}
			list.Add(al1);
			list.Add(al2);
			return list;
		}
		public string Name { get { return "Random"; } }
		public bool Equals(IReproducer other) { return GetType().Equals(other.GetType()); }
	}
	public class RandomSplitReproducer : IReproducer
	{
		private Random rand = new Random();
		public ICollection<IActionList> Reproduce(IActionList father, IActionList mother)
		{
			List<IActionList> list = new List<IActionList>();
			int max = Math.Max(father.Count, mother.Count);
			int split = rand.Next(max);
			ActionList al1 = new ActionList(father.Race);
			ActionList al2 = new ActionList(father.Race);
			for (int c = 0; c < max; c++)
			{
				IAction a1 = null;
				IAction a2 = null;
				if (c < father.Count) a1 = father[c];
				if (c < mother.Count) a2 = mother[c];
				bool takeFatherAction = c < split;
				if (takeFatherAction)
				{
					if (a1 != null) al1.AddAction(a1);
					if (a2 != null) al2.AddAction(a2);
				}
				else
				{
					if (a1 != null) al2.AddAction(a1);
					if (a2 != null) al1.AddAction(a2);
				}
			}
			list.Add(al1);
			list.Add(al2);
			return list;
		}
		public string Name { get { return "RandomSplit"; } }
		public bool Equals(IReproducer other) { return GetType().Equals(other.GetType()); }
	}

	public interface IMutater : IEquatable<IMutater>
	{
		IActionList Mutate(IActionList al);
		string Name { get; }
	}
	public class DefaultMutater : IMutater
	{
		public IActionList Mutate(IActionList al) { return new ActionList(al); }
		public string Name { get { return "Default"; } }
		public bool Equals(IMutater other) { return GetType().Equals(other.GetType()); }
	}
	public class RandomAddActionMutater : IMutater
	{
		private Random rand = new Random();
		public double MutationRate = 0.1;
		public IList<IAction> Actions;
		public RandomAddActionMutater(double mutationRate, IList<IAction> actions)
		{
			Actions = actions;
			MutationRate = mutationRate;
		}
		public IActionList Mutate(IActionList al)
		{
			ActionList mutation = new ActionList(al.Race);
			foreach (IAction action in al)
			{
				double value = rand.NextDouble();
				if (value <= MutationRate)
				{
					mutation.AddAction(Actions[rand.Next(Actions.Count)]);
				}
				mutation.AddAction(action);
			}
			return mutation;
		}
		public string Name { get { return "RandomAdd"; } }
		public bool Equals(IMutater other) { return GetType().Equals(other.GetType()); }
	}
	public class RandomRemoveActionMutater : IMutater
	{
		private Random rand = new Random();
		public double MutationRate = 0.1;
		public RandomRemoveActionMutater(double mutationRate)
		{
			MutationRate = mutationRate;
		}
		public IActionList Mutate(IActionList al)
		{
			ActionList mutation = new ActionList(al.Race);
			foreach (IAction action in al)
			{
				double value = rand.NextDouble();
				if (value > MutationRate)
					mutation.AddAction(action);
			}
			return mutation;
		}
		public string Name { get { return "RandomRemove"; } }
		public bool Equals(IMutater other) { return GetType().Equals(other.GetType()); }
	}
	public class RandomMoveActionMutater : IMutater
	{
		private Random rand = new Random();
		public double MutationRate = 0.1;
		public RandomMoveActionMutater(double mutationRate)
		{
			MutationRate = mutationRate;
		}
		public IActionList Mutate(IActionList al)
		{
			ActionList mutation = new ActionList(al.Race);
			for (int c = 0; c < al.Count; c++)
			{
				IAction action = al[c];
				double value = rand.NextDouble();
				if (value > MutationRate)
				{
					mutation.AddAction(action);
				}
				else
				{
					int index = 0;
					int min = 0;
					IList<IAction> requirements = action.AllRequirements;
					if (requirements != null)
					{
						foreach (IAction required in requirements)
						{
							int tmp = mutation.IndexOf(required);
							index = Math.Max(index, tmp);
							min = Math.Min(min, tmp);
						}
					}
					if (min == -1 || index + 1 >= mutation.Count)
						mutation.AddAction(action);
					else
					{
						mutation.Insert(index + 1, action);
					}
				}
			}
			return mutation;
		}
		public string Name { get { return "RandomMove"; } }
		public bool Equals(IMutater other) { return GetType().Equals(other.GetType()); }
	}

	public class BuildOrderComparer : IComparer<BuildOrderResult>
	{
		public static BuildOrderComparer Instance = new BuildOrderComparer();

		public int Compare(BuildOrderResult x, BuildOrderResult y)
		{
			int compare = -x.Score.CompareTo(y.Score);
			if (compare != 0) return compare;
			if (x.Score != 0)
			{
				compare = x.Time.CompareTo(y.Time);
				if (compare != 0) return compare;
				compare = x.ActionList.Count.CompareTo(y.ActionList.Count);
				if (compare != 0) return compare;
			}
			compare = -(x.Minerals + x.Gas).CompareTo(y.Minerals + y.Gas);
			return compare;
		}
	}

	public class BuildOrderResult
	{
		public IActionList ActionList;
		public double Score;
		public int Time;
		public int Minerals;
		public int Gas;
	}

	public class BuildOrderFinder
	{
		public List<Scouting> m_Scouting = new List<Scouting>();
		private Random m_Random = new Random();
		private List<IAction> m_Actions;
		public List<IAction> m_AutoActions;
		private List<IAction> m_UsefullActions;
		private List<IAction> m_NeededActions;
		private IGoal m_Goal;
		public IRace Race { get { return m_Race; } }
		private IRace m_Race;
		private IState m_Initial;

		//private bool m_BestChanged;
		private BuildOrderResult m_BestResult;
		private IBuildOrder m_Best;
		private List<BuildOrderResult> m_Subset;
		public List<IReproducer> m_Reproducers;
		public List<IMutater> m_Mutaters;

		//private double m_MutationRate = 0.1;
		public int m_FailedCount = 300;
		public int m_MaxActionListSize = 128;
		public int m_SubsetSize = 32;
		public int m_StartDelay = 2;

		public int m_Generation = 0;

		private BuildOrderFinder(IRace race)
		{
			m_Race = race;
			m_Initial = race.InitialState;
			m_Initial.Time = m_StartDelay;
			m_Actions = new List<IAction>(race.Actions);
		}
		public BuildOrderFinder(IRace race, IState goal)
			: this(race)
		{
			m_Goal = new Goal();
			m_Goal.Add(goal);
		}

		public BuildOrderFinder(IRace race, IGoal goals)
			: this(race)
		{
			m_Goal = goals;
		}

		public void GenerateDefaultOperators()
		{
			if (m_Reproducers == null)
			{
				List<IReproducer> reproducers = new List<IReproducer>();
				reproducers.Add(new DefaultReproducer());
				reproducers.Add(new RandomReproducer());
				reproducers.Add(new RandomSplitReproducer());
				reproducers.Add(NewBuildReproducer.Instance);
				m_Reproducers = reproducers;
			}
			if (m_Reproducers.Contains(NewBuildReproducer.Instance))
			{
				NewBuildReproducer.Instance.m_Goal = m_Goal;
				NewBuildReproducer.Instance.m_NeededActions = m_NeededActions;
			}
			if (m_Mutaters == null)
			{
				List<IMutater> mutaters = new List<IMutater>();
				mutaters.Add(new DefaultMutater());
				mutaters.Add(new RandomAddActionMutater(0.30, m_UsefullActions));
				mutaters.Add(new RandomRemoveActionMutater(0.30));
				mutaters.Add(new RandomMoveActionMutater(0.30));
				m_Mutaters = mutaters;
			}
		}

		//private void FillRandom(IActionList al, int size)
		//{
		//   while (al.Count < size)
		//   {
		//      IAction action = m_UsefullActions[m_Random.Next(m_UsefullActions.Count)];
		//      while (action.IsUseless(m_Goal))
		//         action = m_UsefullActions[m_Random.Next(m_UsefullActions.Count)];
		//      al.AddAction(action);
		//   }
		//}

		private ActionList m_BasicActiontList = null;
		private void GenerateSubset()
		{
			m_BasicActiontList = new ActionList(m_Race);
			m_NeededActions = new List<IAction>();
			foreach (IState state in m_Goal)
			{
				IActionList tmp = state.BasicBuildOrder;
				IList<IAction> tmp2 = state.NeededActions;
				if (tmp != null)
					m_BasicActiontList.AddRange(tmp);
				if (tmp2 != null)
					m_NeededActions.AddRange(tmp2);
			}
			m_UsefullActions = new List<IAction>((m_BasicActiontList == null ? m_Race.Actions : new ActionSet(m_BasicActiontList)));
			m_UsefullActions.AddRange(m_Race.EconomyActions);
			for (int c = 0; c < m_UsefullActions.Count; c++)
			{
				IAction action = m_UsefullActions[c];
				IAction[,] variables = action.Requirements;
				if (variables != null)
				{
					for (int d = 0; d < variables.GetLength(0); d++)
						for (int e = 0; e < variables.GetLength(1); e++)
							if (!m_UsefullActions.Contains(variables[d, e]))
								m_UsefullActions.Add(variables[d, e]);
				}
			}
			GenerateDefaultOperators();
			IState copy = null;
			if (m_Subset == null) m_Subset = new List<BuildOrderResult>();
			else m_Subset.Clear();

			string filename = m_Initial.Race.Name + ".BuildOrders.xml";
			if (File.Exists(filename))
			{
				XmlDocument buildOrders = new XmlDocument();
				buildOrders.Load(filename);
				XmlNodeList files = buildOrders.SelectNodes("BuildOrders/File");
				foreach (XmlNode node in files)
				{
					filename = node.Attributes["Name"].Value;
					ActionList actionList = new ActionList(m_Race);
					actionList.Load(filename);
					actionList.AppendMissingAndRemoveExceeding(m_NeededActions);
					TestActionList(actionList, m_Subset);
				}
			}
			//List<IActionList> actionLists = ActionList.GenerateVariablesActionLists(m_NeededActions);
			//foreach (IActionList actionList in actionLists)
			//{
			//   TestActionList(actionList, m_Subset);
			//}

			for (; m_Subset.Count < m_SubsetSize; )
			{
				ActionList al = new ActionList(m_Race);
				foreach (IState state in m_Goal)
				{
					IActionList tmp = state.BasicBuildOrder;
					if (tmp != null) al.AddRange(tmp);
				}
				al.AppendMissingAndRemoveExceeding(m_NeededActions);
				copy = m_Initial.Clone();
				copy.FailedCount = m_FailedCount;
				IBuildOrder bo = copy.ExecuteActionList(al, m_Goal, m_AutoActions, new List<Scouting>(m_Scouting));
				BuildOrderResult result = new BuildOrderResult();
				result.ActionList = bo.ActionList;
				result.Time = bo.State.Time;
				result.Score = bo.Score;
				result.Minerals = (int)bo.State.Minerals;
				result.Gas = (int)bo.State.Gas;
				m_Subset.Add(result);
			}
		}

		private void TestActionList(IActionList actionList, List<BuildOrderResult> bests)
		{
			m_GameTested++;
			IState copy = m_Initial.Clone();
			copy.FailedCount = m_FailedCount;
			IBuildOrder bo = copy.ExecuteActionList(actionList, m_Goal, m_AutoActions, new List<Scouting>(m_Scouting));
			BuildOrderResult result = new BuildOrderResult();
			result.ActionList = bo.ActionList;
			result.Score = bo.Score;
			result.Time = bo.State.Time;
			result.Minerals = (int)bo.State.Minerals;
			result.Gas = (int)bo.State.Gas;
			lock (bests)
			{
				bests.Add(result);
			}
			lock (bests)
			{
				if (bests.Count > m_SubsetSize)
				{
					bests.Sort(BuildOrderComparer.Instance);
					while (bests.Count > m_SubsetSize)
						bests.RemoveAt(m_SubsetSize);
				}
			}
			lock (this)
			{
				if (m_BestResult == null || BuildOrderComparer.Instance.Compare(result, m_BestResult) < 0)
				{
					m_BestResult = result;
					m_Best = bo;
				}
			}
		}

		public delegate void PercentageChanged(double precentage);

		public class BuildOrderFinderWorker
		{
			public readonly ManualResetEvent DoneEvent = new ManualResetEvent(false);
			private BuildOrderFinder m_Finder;
			private List<BuildOrderResult> m_NewSubset;

			public BuildOrderFinderWorker(BuildOrderFinder finder, List<BuildOrderResult> newSubset)
			{
				m_Finder = finder;
				m_NewSubset = newSubset;
			}

			public void Run(Object threadContext)
			{
				IActionList actionList = threadContext as IActionList;
				m_Finder.TestActionList(actionList, m_NewSubset);
				DoneEvent.Set();
			}
		}

		public int m_GameTested = 0;
		public IBuildOrder NextGeneration(PercentageChanged onPercentageChanged)
		{
			if (m_Subset == null)
			{
				if (m_AutoActions != null && m_AutoActions.Count > 0)
					foreach (IAction action in m_AutoActions)
						m_Actions.Remove(action);
				GenerateSubset();
			}
			m_GameTested = 0;
			m_Generation++;
			HashSet<IActionList> actionLists = new HashSet<IActionList>();
			IBuildOrder lastBest = m_Best;
			List<BuildOrderResult> newSubset = new List<BuildOrderResult>();
			List<ManualResetEvent> doneEvents = new List<ManualResetEvent>();
			int estimation = m_Subset.Count * m_Subset.Count * m_Reproducers.Count * m_Mutaters.Count;
			int count = 0;
			int lastUpdate = -1;
			for (int c = 0; c < m_Subset.Count - 1; c++)
			{
				for (int d = c + 1; d < m_Subset.Count; d++)
				{
					IActionList al1 = m_Subset[c].ActionList;
					IActionList al2 = m_Subset[d].ActionList;
					List<IActionList> familly = new List<IActionList>();
					foreach (IReproducer reproducer in m_Reproducers)
					{
						familly.AddRange(reproducer.Reproduce(al1, al2));
					}
					foreach (IActionList actionList in familly)
					{
						foreach (IMutater mutater in m_Mutaters)
						{
							if (onPercentageChanged != null && lastUpdate < (m_GameTested / 256))
							{
								lastUpdate = (m_GameTested / 256);
								onPercentageChanged(count / (double)estimation);
							}
							IActionList mutatedActionList = mutater.Mutate(actionList);
							mutatedActionList.AppendMissingAndRemoveExceeding(m_NeededActions);
							if (!actionLists.Contains(mutatedActionList))
							{
								actionLists.Add(mutatedActionList);
								BuildOrderFinderWorker worker = new BuildOrderFinderWorker(this, newSubset);
								doneEvents.Add(worker.DoneEvent);
								ThreadPool.QueueUserWorkItem(worker.Run, mutatedActionList);
							}
							count++;
						}
					}
				}
			}
			int max = doneEvents.Count;
			int countLoop = 0;
			while (doneEvents.Count > 0)
			{
				countLoop++;
				int value = max - doneEvents.Count;
				if (onPercentageChanged != null && (countLoop % 4 == 0)) onPercentageChanged(value / (double)max);
				ManualResetEvent[] array = null;
				if (doneEvents.Count <= 64)
				{
					array = doneEvents.ToArray();
					doneEvents.Clear();
				}
				else
				{
					array = new ManualResetEvent[64];
					for (int c = 0; c < 64; c++)
						array[c] = doneEvents[c];
					doneEvents.RemoveRange(0, 64);
				}
				WaitHandle.WaitAll(array);
			}
			m_Subset = newSubset;
			return m_Best;
		}
	}
}
